//
// Created by liushuai on 2021/1/30.
//

#include "pathSum.h"

void pathSum(TreeNode *root, vector<int> &cache, vector<vector<int>> &paths, int value) {
    if (!root)
        return;
    cache.push_back(root->val);
    if (!root->left && !root->right && value - root->val == 0)
        paths.push_back(cache);

    pathSum(root->left, cache, paths, value - root->val);
    pathSum(root->right, cache, paths, value - root->val);
    cache.pop_back();//左右节点均不合适，此时节点应该被剔除

}

vector<vector<int> > pathSum(TreeNode *root, int value) {
    vector<int> cache;
    vector<vector<int>> result;
    pathSum(root, cache, result, value);
    return result;
}